package algorithms.sort;

import java.util.Arrays;

/**
 * <h1>归并排序</h1>
 * <p>
 * 归并排序是建立在归并操作上的一种有效的排序算法
 * </p>
 * <h2>算法思想</h2>
 * <p>
 * 分治法+有序序列的merge操作：
 * <ul>
 * 从概念上讲，合并排序的工作原理如下：
 * <li>将未排序的列表分成n个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。</li>
 * <li>重复合并子列表以生成新的已排序子列表，直到只剩下1个子列表。 这将是有序列表。</li>
 * </ul>
 * </p>
 * <p>
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 对序列递归划分，然后对划分后的有序序列进行归并操作，直到整个序列有序。是从最小有序序列（单个元素）开始归并。
 * </p>
 * 
 * @author shaoyuxia
 *
 * @param <T>
 */
public class MergeSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		T[] result = Arrays.copyOf(a, a.length);
		mergeSort(a, 0, a.length - 1, result);
		result = null;
		return a;
	}

	void mergeSort(T[] a, int start, int end, T[] tmp) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(a, start, mid, tmp);
			mergeSort(a, mid + 1, end, tmp);
			mergeArray(a, start, mid, end, tmp);
		}
	}

	/**
	 * 归并两个有序子序列
	 * 
	 * @param a
	 * @param start
	 * @param mid
	 * @param end
	 * @param tmp
	 */
	private void mergeArray(T[] a, int start, int mid, int end, T[] tmp) {
		int i = start, j = mid + 1, k = start;
		while (i <= mid && j <= end) {
			if (a[i].compareTo(a[j]) < 0) {
				tmp[k++] = a[i++];
			} else {
				tmp[k++] = a[j++];
			}
		}
		while (i <= mid) {
			tmp[k++] = a[i++];
		}
		while (j <= end) {
			tmp[k++] = a[j++];
		}
		// 反映排序后结果到原数组
		for (int n = start; n <= end; n++) {
			a[n] = tmp[n];
		}

	}

}
